/*
 * ScarfComplex.java
 *
 * Created on January 7, 2004, 8:59 PM
 */

package com.milowski.monos.monomial;

import java.util.*;
import java.util.logging.*;

/**
 * A computation object for computing the Scarf Complex of a generic artinian
 * monomial ideal.
 * @author  R. Alexander Milowski
 */
public class ScarfComplex {

   static Logger log = Logger.getLogger("com.milowski.monos.monomial");
   
   class Facet {
      short parentVar;
      short lastDrop;
      Facet parent;      
      short [] contributor;
      Monomial [] vertices;
      Facet(int size) {
         parent = null;
         lastDrop = -1;
         contributor = new short[size];
         for (int i=0; i<contributor.length; i++) {
            contributor[i] = (short)0;
         }
         vertices = new Monomial[size];
      }
      
      void initialize() {
         for (int i=0; i<vertices.length; i++) {
            for (int j=0; j<contributor.length; j++) {
               if (vertices[i].getValues()[j]>vertices[contributor[j]].getValues()[j]) {
                  contributor[j] = (short)i;
               }
            }
         }
      }
      
      Facet move(short var) {
         /*
         System.out.print("At");
         for (int i=0; i<contributor.length; i++) {
            System.out.print(" "+vertices[contributor[i]].getValues()[i]);
         }
         System.out.println();
         System.out.println("Dropping "+var+": ");
          */
         lastDrop = var;
         short vertexVarIndex = contributor[var];
         //System.out.println("   Contributor Index="+vertexVarIndex);
         short newContributor = vertexVarIndex==0 ? (short)1 : (short)0;
         for (short i=0; i<vertices.length; i++) {
            if (i!=vertexVarIndex && vertices[i].getValues()[var]>vertices[newContributor].getValues()[var]) {
               newContributor = i;
            }
         }
         
         //System.out.println("   New Contributor Index="+newContributor);
         if (vertices[newContributor].getValues()[var]==0) {
            //System.out.println("   Zero contribution, returning null.");
            return null;
         }
         
         short conflictVar = 0;
         while (newContributor!=contributor[conflictVar] || conflictVar==var) {
            conflictVar++;
         }
         //System.out.println("   Conflict Var="+conflictVar);
         Iterator monomials = minimal.iterator();
         Monomial best = null;
         while (monomials.hasNext()) {
            Monomial m = (Monomial)monomials.next();
            //System.out.println("   checking: "+m);
            short [] mvalues = m.getValues();
            boolean ok = true;
            for (short i=0; ok && i<mvalues.length; i++) {
               if (i!=conflictVar) {
                  if (mvalues[i]>=vertices[i==var ? newContributor : contributor[i]].getValues()[i]) {
                     //System.out.println("   "+mvalues[i]+" >= "+vertices[i==var ? newContributor : contributor[i]].getValues()[i]+" -> bad");
                     ok = false;
                  }
               } else if (mvalues[i]==0) {
                  //System.out.println("   zero contribution for conflict -> bad");
                  ok = false;
               }
            }
            if (ok) {
               //System.out.println("   match: "+m);
               if (best==null || mvalues[conflictVar]<best.getValues()[conflictVar]) {
                  best = m;
                  //System.out.println("   best updated");
               }
            }
         }
         Facet next = new Facet(contributor.length);
         for (short i=0; i<contributor.length; i++) {
            next.contributor[i] = contributor[i];
            next.vertices[i] = vertices[i];
         }
         next.contributor[var] = newContributor;
         next.contributor[conflictVar] = vertexVarIndex;
         next.vertices[vertexVarIndex] = best;
         next.parent = this;
         next.parentVar = conflictVar;
         return next;
      }
      
      Monomial toMonomial() {
         short [] mvalues = new short[contributor.length];
         for (int i=0; i<mvalues.length; i++) {
            mvalues[i] = vertices[contributor[i]].getValues()[i];
         }
         return new Monomial(mvalues);
      }
   }
   
   LexOrderedList minimal;
   short width;
   
   /** 
    * Creates a new instance from the minimal generators of a monomial ideal.
    * @param minimal The minimal generating set of the ideal.
    */
   public ScarfComplex(LexOrderedList minimal) {
      this.minimal = minimal;
      this.width = (short)((Monomial)minimal.get(0)).getValues().length;
   }
   
   /**
    * Calculates the decomposition given the largest facet label.
    */
   public MonomialTree getDecomposition(Monomial largestFacet) {
      short [] fvalues = largestFacet.getValues();
      Iterator monomials = minimal.iterator();
      Facet rootFacet = new Facet(fvalues.length);
      while (monomials.hasNext()) {
         Monomial m = (Monomial)monomials.next();
         for (int i=0; i<fvalues.length; i++) {
            if (m.getValues()[i]==fvalues[i]) {
               rootFacet.vertices[i] = m;
               rootFacet.contributor[i] = (short)i;
            }
         }
      }
      for (int i=0; i<rootFacet.vertices.length; i++) {
         if (rootFacet.vertices[i]==null) {
            throw new RuntimeException("Algorithm failure: Contributor could not be found for variable "+i+", largest="+largestFacet);
         }
      }
      MonomialTree mtree = new MonomialTree(minimal.getLexOrder());
      int facetCount = 1;
      if (log.isLoggable(Level.FINER)) {
         log.finer("  New Facet: "+largestFacet);
      }
      long startTime = System.currentTimeMillis();
      mtree.add(largestFacet,null);

      Facet current = rootFacet;
      do {
         short var = current.lastDrop;
         if (var<0) {
            var = 0;
         } else {
            var++;
         }
         if (var<width) {
            Facet next=null;
            Monomial label = null;
            for (; next==null && var<width; var++) {
               next = current.move(var);
               if (next!=null) {
                  label = next.toMonomial();
                  if (mtree.contains(label)) {
                     next = null;
                  }
               }
            }
            if (next==null) {
               current = current.parent;
            } else {
               facetCount++;
               if (log.isLoggable(Level.FINER)) {
                  log.finer("  New Facet: "+label);
               } else if (log.isLoggable(Level.FINE) && facetCount%10000==0) {
                  log.fine("  Facets found: "+facetCount);
               }
               mtree.add(label,null);
               current = next;
            }
         } else {
            current = current.parent;
         }
      } while (current!=null);
      
      if (log.isLoggable(Level.FINE)) {
         log.fine("  Facets found: "+facetCount);
         log.fine("Elapsed Time = "+(System.currentTimeMillis()-startTime));
      }
      
      return mtree;
   }
   
   
}
